#include <string>
#include <map>
#include <fstream>
#include <algorithm>
#include <iostream>
#include <vector>

namespace part2
{

    std::size_t getMiniMultiple(std::size_t val1, std::size_t val2)
    {
        if (val1 == val2)
            return val1;

        std::size_t minVal {val1 > val2 ? val2 : val1};
        std::size_t maxVal {val1 < val2 ? val2 : val1};

        std::size_t multiple {minVal};
        while (multiple < maxVal)
            multiple += minVal;

        while (true)
        {
            if (multiple % maxVal == 0)
                return multiple;
            multiple += minVal;
        }
    }

    enum class Instruction
    {
        LEFT,
        RIGHT,
    };

    class Network
    {
        using Nexts = std::pair<std::string, std::string>;

    public:
        Network(std::ifstream& file) :  _beginNodes{}, _paths{}
        {
            std::string line;

            while (std::getline(file, line))
            {
                std::string node {line.substr(0, 3)};
                if (node.back() == 'A')
                    this->_beginNodes.emplace_back(node);

                std::size_t leftNodeIdx {line.find('(') + 1};
                std::string leftNode {line.substr(leftNodeIdx, 3)};
                
                std::size_t rightNodeIdx {line.find(',') + 2};
                std::string rightNode {line.substr(rightNodeIdx, 3)};

                this->_paths.emplace(
                    std::move(node), std::make_pair(std::move(leftNode), std::move(rightNode))
                );
            }
        }

    public:
        std::size_t getStepSize(const std::vector<Instruction>& instructions,
                                const std::string* beginNode) const
        {
            std::size_t stepSize {0};
            const std::string* currentNode {beginNode};
            while (true)
            {
                for (Instruction ins : instructions)
                {
                    if (currentNode->back() == 'Z')
                        return stepSize;
                    const Nexts& next {this->_paths.find(*currentNode)->second};
                    currentNode = (ins == Instruction::LEFT ? &next.first : &next.second); 
                    stepSize += 1;
                }
            }
        }

        std::size_t getStepSize(const std::vector<Instruction>& instructions) const
        {
            std::size_t stepSize {this->getStepSize(instructions, this->_beginNodes.data())};
            for (std::size_t i = 1; i < this->_beginNodes.size(); ++i)
                stepSize = getMiniMultiple(
                    this->getStepSize(instructions, &(this->_beginNodes[i])), stepSize
                );

            return stepSize;
        }

        void print() const
        {
            std::cout << "Begin nodes: ";
            for (const std::string& node : this->_beginNodes)
                std::cout << node << ' ';
            std::cout << std::endl;

            // for (const auto& path : this->_paths)
            // {
            //     std::cout << path.first << " => "
            //               << '(' << path.second.first << ','
            //               << ' ' << path.second.second << ')' << std::endl;
            // }
        }

    private:
        std::vector<std::string> _beginNodes;
        std::map<std::string, Nexts> _paths;
    };

    std::vector<Instruction> getInstructions(const std::string& line)
    {
        std::vector<Instruction> instructions{};
        for (const char ch : line)
            instructions.emplace_back(ch == 'L' ? Instruction::LEFT : Instruction::RIGHT);
        return instructions;
    }

    void solute()
    {
        std::ifstream file {"./src/day08/input.txt"};
        std::string line;
        std::getline(file, line);

        std::vector<Instruction> instructions {getInstructions(line)};
        std::getline(file, line);

        Network network {file};
        network.print();

        std::cout << network.getStepSize(instructions) << std::endl;
    }
}
